package algorithms.sorts;

import algorithms.Utils;

import java.util.Arrays;

public class CountingSort {
    public static void main(String[] args) {

        //int[] arr = Utils.randomArray(100000000, -2000, 2000);
        int[] arr = Utils.randomArray(100000000, -100000, 100000);
        //System.out.println(Arrays.toString(arr));
        long start = System.currentTimeMillis();
        System.out.println("heapSort start:" + start);
        countingSort(arr);
        long end = System.currentTimeMillis();
        System.out.println("  heapSort end:" + end);
        System.out.println("  heapSort use:" + (end - start));
        System.out.println(Utils.isAscend(arr));
        //System.out.println(Arrays.toString(arr));
    }

    private static void countingSort(int[] arr) {
        int minIdx = 0, maxIdx = 0;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < arr[minIdx]) {
                minIdx = i;
            } else if (arr[i] > arr[maxIdx]) {
                maxIdx = i;
            }
        }
        int min = arr[minIdx];
        int max = arr[maxIdx];

        int[] buckets = new int[max - min + 1];
        for (int e : arr) {
            buckets[e - min]++;
        }

        for (int i = 0, k = 0; i < buckets.length; i++) {
            int count = buckets[i];
            for (int j = 0; j < count; j++) {
                arr[k++] = i + min;
            }
        }
    }
}
